
#include <forward_list>
#include <vector>
#include <list>
#include <iostream>
#include <climits>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

using namespace std;

int particionK  = 0;
vector<int> grafoAdj;
int V = 0;


typedef struct {
	//particiones creadas
	vector< list<int> > particiones;
	int p_count;
	int peso_total;
} result;

void putEje(int x,int y, int w){
	if (x> y) swap(x,y);
	//cout << "put eje "<<x << " "<< y << " -- " << ( x*y)+y << " en "<< w << "\n";
	grafoAdj[ ( x*V)+y] = w;
}

int getEje(int x,int y){
	if (x> y) swap(x,y);
	//cout << "get eje " <<x << " "<< y << " -- " << ( x*y)+y << " en "<< grafoAdj[( x*y)+y] << "\n";
	return grafoAdj[( x*V)+y];
}
void debugResult(result *r){

	cout << "p_count : " << r->p_count ;
	cout << " peso_total :" << r->peso_total << "\n";

	int p=0;
	for (auto it= r->particiones.begin();it!= r->particiones.end(); ++it){
		cout << "particion : " <<  p  << " = ";

		for (auto t=it->begin(); t != it->end(); ++t){			
			cout << " " << *t ;				
			
		}
		cout <<  "\n";		
		p++;
	}			
	cout << "\n";
}
void actualizarPeso(result & r, int particion, int v){

	if  (r.peso_total == INT_MAX)
		r.peso_total = 0;
	
	int p;
	for(auto it = r.particiones[particion].begin() ; it != r.particiones[particion].end();++it){
		if (v != *it){

			p = getEje(v,*it);
//			cout << "peso "<< p << " de "<< v << " : "<< *it <<"\n";
			r.peso_total += p;
		}

			
	}
//	cout << "sale de actualizar peso "<< r.peso_total << "\n" ;
}


void particion(result  &r, forward_list<int> disponibles){

    forward_list<int> dispParam;
    forward_list<int>::iterator minI;
    result resParam, minRes;
    minRes.peso_total = INT_MAX;
	//cout << "---------------------- \n";

    int d_size = distance(begin(disponibles), end(disponibles));
    //cout << "entro a particion con " << d_size << " disponibles \n" ;
	for(auto it = disponibles.begin(); it != disponibles.end();++it){
		dispParam = disponibles;
		dispParam.remove(*it);

		//cout << "loop   "<< *it << " \n";
		//no es necesario que obligatoriamente ubique el vertice en una particion nueva
		if (r.p_count > 0 ){
			/*para cada particion creada
			agrego el vertice a la particion y calculo el peso peso_total
			si es mejor que el existente actualizo peso */			
			for(int i=0 ; i< r.p_count; i++){
				resParam  = r;
				resParam.particiones[i].push_front(*it);
				actualizarPeso(resParam,i,*it);
	//			cout << "desp de actualizar peso " << resParam.peso_total << "\n";
				if (resParam.peso_total < minRes.peso_total){
	// 				if (d_size > 1 ){
	// 					particion(resParam,dispParam);
	// //					cout << "volvio con "<< resParam.peso_total <<"\n";
	// 				}					
					if (resParam.peso_total < minRes.peso_total){
	//					cout << "actualizo "<< resParam.peso_total << "\n";
	//					cout << *it <<" min I \n";
						minRes = resParam;
						minI = it;
					}
				}
			}
		}
		
		// si aun se pueden agregar particiones pruebo agregando 
		//una particion
		if ( particionK > r.p_count ){			
			resParam  = r;
			resParam.particiones[resParam.p_count].push_front(*it);
			resParam.p_count += 1;
 			actualizarPeso(resParam,resParam.p_count-1,*it);
	//		cout << " llamo recursivamente "  ;
	//		cout  << *it << " "<< resParam.peso_total <<  " \n";

			if (resParam.peso_total < minRes.peso_total){
	//			cout << "actualizo "<< resParam.peso_total << "\n";
				minRes = resParam;				
	//			cout << *it <<" min I \n";
				minI = it;
			}
		}
	}

	//cout << "salgo con " << minRes.peso_total <<  " entre con  " << r.peso_total << "\n";
	r = minRes;
	if (d_size > 1){
		disponibles.remove(*minI);
	//	cout << "remuevo " << *minI << "\n";
	//	debugResult(&r);		
		particion(r, disponibles);
	}

}

/*
- sea R una solucion con I particiones  
- sea C la  lista de vertices todabia no ubicados en alguna particion
  para cada uno de estos vertices tomo uno y lo retiro de la lista

	- si puedo agregar una particion mas agrego una particion
	  solo con el vertice que retire y llamo recursivamente

	- si puedo no agregar una particion agrego el vertice que retire 
	   a cada una de las particiones para luego llamar recursivamente
    
    - si alguna de las soluciones que evalue es mejor que la mejor conocida
    me quedo con esa solucion.

*/

void printResult(result *r){

	int p = 0;
	for (int i=0; i< V ; i++){
		p = 0;
		for (auto it= r->particiones.begin();it!= r->particiones.end(); ++it){
			
			for (auto t=it->begin(); t != it->end(); ++t){
				if ( *t == i ){
					cout <<  p << " "  ;
					break;
				}
			}
			
			p++;
		}			
	}
	cout << "\n";
}

int main(int argc, char** argv) {	

    char line[1000];
    char* strVal;
    int val;
    int readedLine = -1;
    vector <int> instanceTitle(3);
    vector< vector<int> > values;
    int vertices;
    int aristas;
    int k,u,v,w;
    result r;
	forward_list<int> d;
	
    while ( cin.getline(line, 999, '\n') ) {
    	//cout << "while |" << readedLine <<   "| "<< line << "|\n";
    	//if (readedLine == 0 and
        if (readedLine == 0) {   

            readedLine -= 1;
            r.p_count = 0;
        	r.particiones.resize(particionK);

			for (auto it= r.particiones.begin();it!= r.particiones.end(); ++it){								
					it->clear();					
			}			        		
        	
			r.peso_total = INT_MAX;				
			cout << "\n--------------------------\n";
			cout << "vertices : " << V << " aristas :" << aristas << " k :"<< particionK<< "\n";
		    particion(r,d);	
            d.resize(0);        
            printResult(&r);            
            debugResult(&r);            
            if ( line[0] == '0') break;
        }
        if (readedLine == -1 and line[0] != '0') {        	        	
        	d.resize(0);       
            strVal = strtok(line, " ");
            V = atoi(strVal);

            strVal = strtok(NULL, " ");
            aristas = atoi(strVal);

            strVal = strtok(NULL, " ");
            particionK = atoi(strVal);

            readedLine = aristas;
		
			grafoAdj.resize( V*V,0 ) ;
			for (int i=0; i<V ; i++){
				d.push_front(i);
			}
        } else {
        	strVal = strtok(line, " ");
            u = atoi(strVal);

            strVal = strtok(NULL, " ");
            v = atoi(strVal);

            strVal = strtok(NULL, " ");
            w = atoi(strVal);
            putEje(u,v,w);   
            readedLine -= 1;            
        }
    }
    return 0;
}
